#include "heapq.h"

#include <stdlib.h>
#include <string.h>
#include <assert.h>

void heapq_init(heapq *h, size_t element_size, heapq_compare_fn cmp, 
    vector_cons_fn cons_fn, vector_free_fn free_fn, vector_copy_fn copy_fn)
{
    vector_init(&(h->vec), element_size, cons_fn, free_fn, copy_fn);
    h->cmp = cmp;
}

void heapq_free(heapq *h)
{
    vector_free(&(h->vec));
    h->cmp = NULL;
}

int heapq_size(const heapq *h)
{
    return vector_size(&(h->vec));
}

bool heapq_empty(const heapq *h)
{
    return vector_empty(&(h->vec));
}

void heap_adjust_bot2top(heapq *h) {
    vector *v = &(h->vec);
    size_t cur = vector_size(v);   // cur = 下标 + 1

    while (cur > 1)
    {
        size_t parent = cur / 2 - 1, child = cur - 1;
        if (h->cmp(vector_at(v, child), vector_at(v, parent)) > 0)   // child > parent
        {
            vector_swap(v, parent, child);
            cur /= 2;
        }
        else 
            break;
    }
}

void heapq_push(heapq *h, const void *element)
{
    vector_push_back(&(h->vec), element);
    heap_adjust_bot2top(h);
}

void *heapq_top(heapq *h)
{
    assert(!vector_empty(&(h->vec)));
    return vector_at(&(h->vec), 0);
}

void heap_adjust_top2bot(heapq *h) {
    vector *v = &(h->vec);
    size_t cur = 1;   // cur = 下标 + 1

    while (cur * 2 <= v->size)  // 尚有孩子存活
    {
        size_t parent = cur - 1, lchild = cur * 2 - 1, rchild = cur * 2;
        void *lc = vector_at(v, lchild), *rc, *pa = vector_at(v, parent);
        void *max_node = pa;

        if (rchild < v->size)
            rc = vector_at(v, rchild);
        // 找最大者
        if (h->cmp(lc, max_node) > 0)
            max_node = lc;
        if (rchild < v->size && h->cmp(rc, max_node) > 0) {
            max_node = rc;
        }

        if (h->cmp(lc, max_node) == 0)   // 左孩子最大
        {
            vector_swap(v, parent, lchild);
            cur *= 2;
        }
        else if (rchild < v->size && h->cmp(rc, max_node) == 0) {
            vector_swap(v, parent, rchild);
            cur = cur * 2 + 1;
        }
        else
            break;
    }
}

void heapq_pop(heapq *h)
{
    vector *v = &(h->vec);
    assert(!vector_empty(v));
    if (v->free_fn)
        v->free_fn(vector_at(v, 0));
    
    vector_set(&(h->vec), 0, vector_at(v, v->size - 1));
    vector_pop_back(v);
    heap_adjust_top2bot(h);
}

void heapq_clear(heapq *h)
{
    vector_clear(&(h->vec));
}
